﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    static class InsertSort
    {
        static void Main()
        {
            Console.WriteLine("insert sort.");
            int[] arr = { 1, 2, 3, 5, 0, 9, 8, 7, 6, 4 };
            Random rd = new Random();
            for (int j = 0; j < 1000; j++)
            {
                for (int i = 0; i < 10; i++)
                {
                    arr[i] = rd.Next(20);
                }
                Sort(arr);
                if (!Utils.CheckOrderArray(arr))
                {
                    Console.WriteLine("error.");
                }
                //Utils.WriteArr(arr);
            }
        }

        //public static void Sort(int[] arr)
        //{
        //    int len = arr.Length;

        //    //默认第一个数是已经排好序的，从第二个开始，依次按大小插入已拍好序的部分中。
        //    for (int i = 1; i < len; i++)
        //    {
        //        int idx = i;//已经排好序的部分个数
        //        int value = arr[i];
        //        for (int j = 0; j < idx; j++)
        //        {
        //            if (value < arr[j])
        //            {
        //                for (int k = idx; k > j; k--)
        //                {
        //                    arr[k] = arr[k - 1];
        //                }
        //                arr[j] = value;
        //                break;
        //            }
        //        }
        //    }
        //}

        //public static void Sort(int[] arr, int gap = 1, int beg = 0)
        //{
        //    int len = arr.Length;

        //    //默认第一个数是已经排好序的，从第二个开始，依次按大小插入已拍好序的部分中。
        //    for (int i = gap; i < len; i += gap)
        //    {
        //        int value = arr[i];
        //        for (int j = beg; j < i; j += gap)
        //        {
        //            if (value < arr[j])
        //            {
        //                for (int k = i; k > j; k -= gap)
        //                {
        //                    arr[k] = arr[k - 1];
        //                }
        //                arr[j] = value;
        //                break;
        //            }
        //        }
        //    }
        //}

        public static void Sort(int[] arr, int gap=1, int beg=0)
        {
            int len = arr.Length;

            //默认第一个数是已经排好序的，从第二个开始，依次按大小插入已拍好序的部分中。
            for (int i = gap + beg; i < len; i += gap)
            {
                int value = arr[i];
                for (int j = i - gap; j >= 0; j -= gap)
                {
                    if (value < arr[j])
                    {
                        arr[j + gap] = arr[j];
                    }
                    else
                    {
                        arr[j + gap] = value;
                        break;
                    }
                }
            }
        }
    }
}
